#pragma once
#include <bits/stdc++.h>

using namespace std;

enum BackgroundColor{
    BLACK = 0,RED=1,
};
template <class T>
struct RBTreeNode{
    typedef RBTreeNode<T>* RBTreeNodePtr;
    
    RBTreeNode(const T&data,BackgroundColor Inicolor =RED)
    : _data(data),left(nullptr),right(nullptr),parent(nullptr),color(Inicolor)
    {
        ;
    }
    T _data;
    RBTreeNodePtr left;
    RBTreeNodePtr right;
    RBTreeNodePtr parent;
    BackgroundColor color;
};
template<class T>
struct DefaultCmp{
    int operator()(const T&a,const T&b)const{
        if(a>b)
        {
            return 1;
        }
        else if(a<b)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
};


template <class T,class Ref,class Ptr>
class RBTreeIterator{
    typedef RBTreeIterator<T,Ref,Ptr> Self;
    typedef RBTreeNode<T>* RBTreeNodePtr;
    RBTreeNodePtr _node;
    RBTreeNodePtr M_min(RBTreeNodePtr x)const
    {
        while(x&&x->left)
            x = x->left;
        return x;
    }
    RBTreeNodePtr M_max(RBTreeNodePtr x)const
    {
        while(x&&x->right)
            x = x->right;
        return x;
    }
    public:
    RBTreeIterator(const RBTreeNodePtr& x)
    : _node(x)
    {
        ;
    }
    RBTreeIterator()
    : _node(nullptr)
    {
        ;
    }
    Ref operator*()const
    {
        return _node->_data;
    }
    Ptr operator->()const
    {
        return &(_node->_data);
    }
    bool operator==(const Self& rhs)const
    {
        return _node == rhs._node;
    }
    bool operator!=(const Self& rhs)const
    {
        return _node!= rhs._node;
    }
    Self operator++()//前置++
    {
        if(_node->right)
        {
            _node = M_min(_node->right);
        }
        else
        {
            //不断向上找，找到不是右子树就可以了
            RBTreeNodePtr p = _node->parent;
            while(p->right==_node)
            {
                _node = p;
                p = p->parent;
            }
            //但是我们不排除一直会找到根节点的情况
            //也就是说，根节点的右子树都不能用
            //分为，根节点右子树还是空，或者不为空
            //我们考虑是空，或者是有节点，其退出时，必然_node都是的值都是m_header的值，用这个值做end()显然是合适的
            //有了这个考量，才有前面将m_header的父亲节点作为m_root的缘由
            if(_node->right != p)//这里就要处理调不是上述情况，那么就是正常退出
                _node = p;

        }
        return *this;
    }
    Self operator++(int)//后置++
    {
        Self temp = this;
        if(_node->right)
        {
            _node = M_min(_node->right);
        }
        else
        {
            //不断向上找，找到不是右子树就可以了
            RBTreeNodePtr p = _node->parent;
            while(p->right==_node)
            {
                _node = p;
                p = p->parent;
            }
            //但是我们不排除一直会找到根节点的情况
            //也就是说，根节点的右子树都不能用
            //分为，根节点右子树还是空，或者不为空
            //我们考虑是空，或者是有节点，其退出时，必然_node都是的值都是m_header的值，用这个值做end()显然是合适的
            //有了这个考量，才有前面将m_header的父亲节点作为m_root的缘由
            if(_node->right != p)//这里就要处理调不是上述情况，那么就是正常退出
                _node = p;

        }
        return temp;
    }
    Self operator--()
    {
        //对应的，因为我们把m_header作为我们的end，所以处理--的时候，我们要特别处理head头节点的情况
        //设置的时候，设置head为红,这里我们额外加个判断
        if(_node->parent->parent==_node && _node->color==RED)
        {
            _node = M_max(_node->right);//head--，就要指向最大的那个节点
        }
        else if(_node->left)
        {
            _node = M_max(_node->left);
        }
        else
        {
            RBTreeNodePtr p = _node->parent;
            while(p->left==_node)
            {
                _node = p;
                p = p->parent;
            }
            if(_node->left!= p)
                _node = p;
        }
        return *this;
    }
    Self operator--(int)
    {
        Self temp = *this;
        //对应的，因为我们把m_header作为我们的end，所以处理--的时候，我们要特别处理head头节点的情况
        //设置的时候，设置head为红,这里我们额外加个判断
        if(_node->parent->parent==_node && _node->color==RED)
        {
            _node = M_max(_node->right);//head--，就要指向最大的那个节点
        }
        else if(_node->left)
        {
            _node = M_max(_node->left);
        }
        else
        {
            RBTreeNodePtr p = _node->parent;
            while(p->left==_node)
            {
                _node = p;
                p = p->parent;
            }
            if(_node->left!= p)
                _node = p;
        }
        return temp;
    }
};
    


template <class KeyType,class T,class KeyOfValue,class Compare = DefaultCmp<KeyType>>
class RBTree{
    typedef RBTreeNode<T>* RBTreeNodePtr;
    typedef RBTree<KeyType,T,KeyOfValue,Compare> M_RBTree;
    typedef RBTreeNode<T> M_RBTreeNode;
    RBTreeNodePtr m_root;
    size_t m_size;
    RBTreeNodePtr m_header;
    KeyOfValue key_ofval;
    Compare cmp;

    RBTreeNodePtr M_min(RBTreeNodePtr x)const
    {
        while(x->left)
            x = x->left;
        return x;
    }
    RBTreeNodePtr M_max(RBTreeNodePtr x)const
    {
        while(x->right)
            x = x->right;
        return x;
    }
    public:
    typedef RBTreeIterator<T, T&,T*> iterator;
    typedef RBTreeIterator<T, const T&,const  T*> const_iterator;
    iterator begin()
    {
        return iterator(M_min(m_root));
    }
    iterator end()
    {
        return iterator(m_header);
    }
    const_iterator begin()const//这里不需要额外取名，在map和set外层取名也可
    {
        return const_iterator(M_min(m_root));
    }
    const_iterator end()const
    {
        return const_iterator(m_header);
    }
    RBTreeNodePtr  RightRotate(RBTreeNodePtr root)//传要传输的旋转的父节点其父亲所指向的那个节点
    {
        RBTreeNodePtr left = root->left;
        RBTreeNodePtr Childright = left->right;
        
        root->left = Childright;
        if(Childright)
        {
            Childright->parent = root;
        }
        //节点之间的值就算交换完毕
        
        left->right = root;
        root->parent = left;

        return left;
    }
    void Rotate(RBTreeNodePtr parent,RBTreeNodePtr(M_RBTree::*Rotatefunc)(RBTreeNodePtr))
    {
        RBTreeNodePtr PP = parent->parent;
        if(PP && PP!=m_header)
        {
            RBTreeNodePtr Child = (this->*Rotatefunc)(parent);
            if(PP->left == parent)
            {
                PP->left = Child;
                Child->parent = PP;
            }
            else
            {
                PP->right = Child;
                Child->parent = PP;
            }
        }
        else//说明遇见了根节点
        {
            m_root= (this->*Rotatefunc)(parent);
            m_root->parent = m_header;
            m_header ->parent = m_root;
        }
    }
    RBTreeNodePtr LeftRotate(RBTreeNodePtr root)
    {
        RBTreeNodePtr right = root->right;
        RBTreeNodePtr Childleft = right->left;

        root->right = Childleft;
        if(Childleft)
        {
            Childleft->parent = root;
        }

        right->left = root;
        root->parent = right;

        return right;
    }
    bool adjust(RBTreeNodePtr Cur,RBTreeNodePtr CurPrt)
    {
        //在节点插入中，Cur一来应该不会是根节点，调整到根节点，直接退出
        //应该说，父亲不应该会空，应为根节点会直接插入

        RBTreeNodePtr CurGrp = CurPrt->parent;
        RBTreeNodePtr CurUnc= nullptr;
        
        while(Cur && Cur!=m_root)//直到不会是根节点
        {
            if(CurPrt->color==BLACK)
            {
                //理论上说，color节点new的时候默认是红，这里防止出现意外操作下
                Cur->color = RED;
                return true;
            }
            //每次的舅舅节点
            if(CurGrp->left==CurPrt)
            {
                CurUnc = CurGrp->right;
            }
            else{
                CurUnc = CurGrp->left;
            }
            if(CurUnc&& CurUnc->color==RED)//舅舅节点是红色，向上调整
            {
                CurPrt->color = BLACK;
                CurUnc->color = BLACK;
                Cur->color = RED;
                //处理祖孙的颜色变化

                Cur = CurGrp;
                Cur->color = RED;
                //调整其父亲，祖父节点，因为每次舅舅节点都会算，就不需要额外调整
                CurPrt = Cur->parent;
                CurGrp = CurPrt->parent;
            }
            else//舅舅节点是黑色
            {
                if(CurPrt==CurGrp->left)
                {
                    if(Cur==CurPrt->left)
                    {
                        //左左，对祖父节点进行右单旋
                        CurGrp->color = RED;
                        CurPrt->color = BLACK;
                        Rotate(CurGrp,&RightRotate);
                    }
                    else{
                        //左右,先对父亲左单旋，再对祖父右单旋
                        //
                        Cur->color = BLACK;
                        CurGrp->color = CurPrt->color = RED;
                        Rotate(CurPrt,&LeftRotate);
                        Rotate(CurGrp,&RightRotate);
                    }
                }
                else if(CurPrt==CurGrp->right)
                {
                    if(Cur==CurPrt->right)
                    {
                        //右右
                        CurGrp->color = BackgroundColor::RED;
                        CurPrt->color = BLACK;
                        Rotate(CurGrp,&LeftRotate);
                    }
                    else
                    {
                        //右左
                        Cur->color = BLACK;
                        CurGrp->color = CurPrt->color = RED;
                        Rotate(CurPrt,&RightRotate);
                        Rotate(CurGrp,&LeftRotate);
                    }
                }
                //不用在进行调整，至此结束
                break;
            }
        }
        return false;
    }
    public:
    void InorderPrint()
    {
        InorderPrintR(m_root);
        cout<<"\n";
    }
    void InorderPrintR(RBTreeNodePtr root)
    {
        if(root==nullptr)
        {
            return ;
        }
        InorderPrintR(root->left);
        cout<<root->_kv.first<<" ,";
        InorderPrintR(root->right);
    }
    RBTree()
    : m_root(nullptr)
    , m_size(0)
    {
        //
        m_header = new M_RBTreeNode(T());
        m_header->left = m_header->right = m_header->parent = nullptr;
        m_header->color = BLACK;
    }
    
    pair<RBTreeNodePtr,bool> insert(const T& data)
    {
        if(nullptr==m_root)
        {
            //让header指向父亲指向根节点，左指向最小，右指向最大
            m_root = new M_RBTreeNode(data,BLACK);
            m_header->left = m_root;
            m_header->right = m_root; 
            //根节点父节点是header
            m_header->parent = m_root;
            m_root->parent = m_header;
            return make_pair(m_root,true);
        }
            RBTreeNodePtr cur = m_root;
            RBTreeNodePtr CurPrt = nullptr;
            RBTreeNodePtr InsertNode = nullptr;
            while(cur)
            {
                if(cmp(key_ofval(cur->_data),key_ofval(data))>0)//大于插入值
                {
                    if(nullptr==cur->left)
                    {
                        InsertNode = cur->left = new M_RBTreeNode(data);
                        cur->left->parent = cur;
                        adjust(cur->left,cur);
                        break;
                    }
                    else
                    {
                        cur = cur->left;
                        CurPrt = cur;
                    }
                }
                else if(cmp(key_ofval(cur->_data),key_ofval(data))<0)
                {
                    if(nullptr==cur->right)
                    {
                        InsertNode  = cur->right = new M_RBTreeNode(data);
                        cur->right->parent = cur;
                        adjust(cur->right,cur);
                        break;
                    }
                    else
                    {
                        cur = cur->right;
                        CurPrt = cur;
                    }
                }
                else
                {
                    return make_pair(cur,false);
                }
            }
            m_root->color= BLACK;
            m_header->left = M_min(m_root);
            m_header->right = M_max(m_root);
            m_size++;
            return make_pair(InsertNode,true);
    }
    // pair<iterator,bool> insert(const T& data)
    // {
    //     if(nullptr==m_root)
    //     {
    //         //让header指向父亲指向根节点，左指向最小，右指向最大
    //         m_root = new M_RBTreeNode(data,BLACK);
    //         m_header->left = m_root;
    //         m_header->right = m_root; 
    //         //根节点父节点是header
    //         m_header->parent = m_root;
    //         m_root->parent = m_header;
    //         return make_pair(m_root,true);
    //     }
    //         RBTreeNodePtr cur = m_root;
    //         RBTreeNodePtr CurPrt = nullptr;
    //         RBTreeNodePtr InsertNode = nullptr;
    //         while(cur)
    //         {
    //             if(cmp(key_ofval(cur->_data),key_ofval(data))>0)//大于插入值
    //             {
    //                 if(nullptr==cur->left)
    //                 {
    //                     InsertNode = cur->left = new M_RBTreeNode(data);
    //                     cur->left->parent = cur;
    //                     adjust(cur->left,cur);
    //                     break;
    //                 }
    //                 else
    //                 {
    //                     cur = cur->left;
    //                     CurPrt = cur;
    //                 }
    //             }
    //             else if(cmp(key_ofval(cur->_data),key_ofval(data))<0)
    //             {
    //                 if(nullptr==cur->right)
    //                 {
    //                     InsertNode  = cur->right = new M_RBTreeNode(data);
    //                     cur->right->parent = cur;
    //                     adjust(cur->right,cur);
    //                     break;
    //                 }
    //                 else
    //                 {
    //                     cur = cur->right;
    //                     CurPrt = cur;
    //                 }
    //             }
    //             else
    //             {
    //                 return make_pair(cur,false);
    //             }
    //         }
    //         m_root->color= BLACK;
    //         m_header->left = M_min(m_root);
    //         m_header->right = M_max(m_root);
    //         m_size++;
    //         return make_pair(InsertNode,true);
    // }
    int height(RBTreeNodePtr root)
    {
        if(root==nullptr)
        {
            return 0;
        }
        int leftheight = height(root->left);
        int rightheight = height(root->right);
        return 1+(leftheight>rightheight?leftheight:rightheight);
    }
};